# 字串排序(牛逼题目, 但是不是很懂)
# https://www.lanqiao.cn/problems/501/learning/
# 2025/2/21

"""解题思路  (原文链接：https://blog.csdn.net/weixin_46266058/article/details/123469287)

长度 len = 1时，我们构造的字符串要形如 a，逆序对个数为 0，交换次数为 0。
当长度 len = 2 时，我们构造的字符串要形如 ba，逆序对个数 0 + 1，交换次数为 1。
当长度 len=3 时，我们构造的字符串要形如 cba，逆序对个数为 0 + 1 + 2 = 3，交换次数为 3。
当长度 len=4 时，我们构造的字符串要形如 dcba，逆序对个数为 0 + 1 + 2 + 3 = 6，交换次数为 6。
⋯
当长度 len=26时，我们构造的字符串得为 zyxwvutsrqponmlkjihgfedcba，逆序对个数为 325，交换次数为 325。

题目中的要求是V最大是10000，所以这个325是远远达不到要求的，所以势必有字符是要重复的。

那接下来我们考虑一个新的问题，在只有a,b,c的情况下，构造出一个长度为7，交换次数最多的字符串，怎么想呢？
给定一个字符串，插入一个字符，逆序对增加的个数=前面比该字符小的字符数量 + 后面比该字符大的字符数量。
所以，每次我们只要插入当前字符串中字符个数最少的字符就好了~所以我们有三种方案cccbbaa,ccbbbaa,ccbbaaa，字符序最小的话，当然是ccbbaaa了。

不过我们现在的问题是：在给定的长度为 L 的字符串，其最大逆序数个数是多少？
为什么要求这个呢，因为当我们找到第一个长度 L ，其最大逆序数>=V时，我们就可以从这个长度产生字符序最小的字符串，而这个 L 也就是最小的长度。
有了上边的例子，我们明白了，一个长度为 L 的字符串里边，要达到最大逆序数，每个字符个数最好是平均分配的，又要字符序最小，个数多的应该是字符
顺序小的。
那么对于给定的长度, 如何计算最大的逆序对的个数?
假设字符串的总长度为 L。由于题目涉及 26 个字母，我们将 L 分成 26 份:
令 a = L // 26 (整数部分)
令 b = L mod 26 (余数)
这意味着在最优构造下，我们可以将 26 个字母的出现次数“均摊“成两种情况:
1. 有 b 个字母出现次数为 a + 1,
2. 其余 26 - b 个字母出现次数为 a。
为什么这样的分布能获得最大逆序对数?在构造逆序对时，如果我们把字符串按降序排列(也就是字典序最大的排列)，那么任何两个不同字母构成的两个位置
都能形成逆序对(因为较大的字母总在前面), 而相同字母之间不形成逆序对。
- 总的两两位置的对数为: L * (L - 1) / 2
- 如果某个字母出现了 f 次, 则其中任意两个字符都不会出现逆序对, 这部分的逆序对个数为: f * (f - 1) / 2
因此, 整个字符串中能够形成的逆序对总数就是:
L * (L - 1) / 2 - SUM(f_i * (f_i - 1) / 2)
采用均衡分布后的具体计算:
- 对于那b个字母，其出现次数为 a+1，不产生逆序对的内部对数为 (a + 1) * a / 2
- 对于其余 26 -b个字母，其出现次数为 a，不产生逆序对的内部对数为 (a - 1) * a /2
所以所有相同字母内部的不产生逆序对的总数为:
s_1 = [b * (a + 1) * a + (26 - b) * a * (a - 1)] / 2
把它从总逆序对的个数中减去, 最大逆序对个数为:
L * (L - 1) / 2 - s_1

在上面我们已经求出了最小的长度L，也就是第一个L使得max(L)=X>=V，那么我们肯定也可以改变字符顺序，构造出逆序对个数为X，X-1......0的字符串。

于是我们可以从字符串的第一个位置往后构造，具体为：

从小到大枚举字符ch(ch∈[a~z])，判断当前位置的字符为ch是否可以构造出长度为len，且逆序对大于等于V的字符串。

我们设当前位置为pos，那么1~pos-1的位置已经构造好了，那么当前选择字符ch可以新增的逆序对个数就是1~pos-1中比ch大的字符个数
对于pos+1~len的位置，我们总共要添加len-pos个字符，且要保证这些字符能够产生最多的逆序对。
我们可以暴力点一个一个插入。
若插入字符x，则产生的逆序对个数（最多）=(1~pos中大于x的字符数量)+（pos后添加的总字符数量-字符x的数量）
最后若第pos个位置放置ch可以构造出长度为len，逆序对个数大于等于V的字符串，我们就令第pos个位置的字符串为ch，继续构造，
否则在pos放下一个字符ch+1，继续构造。


"""


def construct_max_string(V: int) -> str:
    """
    构造满足特定逆序对数目且字典序最大的最短字符串
    输入:
        V: 目标逆序对数（幸运数字）
    输出:
        一个满足要求的字符串（仅由小写字母组成）
    """

    def max_inversions_for_length(length: int) -> int:
        """
        计算给定字符串长度下最大可能的逆序对数
        根据原代码公式，令 a = length // 26, b = length % 26，
        则最大逆序对数为:
          [ (length - (a+1)) * (a+1) * b + (26 - b) * a * (length - a) ] // 2
        """
        a, b = divmod(length, 26)
        return (((length - (a + 1)) * (a + 1) * b) + ((26 - b) * a * (length - a))) // 2

    # 先确定最短字符串的长度，使得最大逆序对数不小于 V
    length = 1
    while True:
        if max_inversions_for_length(length) >= V:
            break
        length += 1

    # prefix_count[i] 记录前面已确定位置中字母 i 的出现次数
    # 下标 1~26 分别代表 'a' ~ 'z'
    prefix_count = [0] * 27
    # current_inversions 用于记录目前已形成的逆序对数
    # 为了在内部函数中修改，采用列表封装
    current_inversions = [0]

    def check_candidate(candidate: int, remaining: int) -> bool:
        """
        尝试在当前空位放入 candidate 对应的字母（1~26 表示 'a'~'z'），
        计算放入后能额外获得的逆序对数（包括当前位置与之前字符构成的逆序对 add1，
        以及剩余 remaining 个位置在最优填充下能达到的逆序对数 add2）。
        若 current_inversions + add1 + add2 >= V，则说明选择 candidate 后后续仍能满足要求，
        此时更新 current_inversions（加上 add1 部分）并返回 True；否则恢复现场返回 False。
        """
        # 计算放入 candidate 后，与之前已经放置的字符形成的额外逆序对数
        add1 = 0
        # 对于所有字母值大于 candidate 的，前面已出现的次数均构成逆序对
        for letter_val in range(26, candidate, -1):
            add1 += prefix_count[letter_val]

        # 暂时将 candidate 放入前缀中
        prefix_count[candidate] += 1

        add2 = 0
        # local_count 用于模拟后续剩余部分最优填充时各字母的出现次数
        local_count = [0] * 27
        # 模拟剩余 remaining 个位置，贪心选择使得每一步能获得最大逆序对数
        for pos in range(1, remaining + 1):
            best_gain = -1
            best_letter = 0
            # num 用于累计前缀中比当前候选字母大的字符总数
            num = 0
            # 枚举所有可能放置的字母，从字典序最大的 'z'（26）到 'a'（1）
            for letter_val in range(26, 0, -1):
                # 对于当前 pos，若放 letter_val 能获得的逆序对数为：
                # (pos - 1 - local_count[letter_val]) + num
                # 其中 (pos - 1 - local_count[letter_val]) 表示后续还能填的比 letter_val 小的字符数量的上界，
                # 而 num 为前缀中比 letter_val 大的字符数
                potential_gain = (pos - 1 - local_count[letter_val] + num)
                if potential_gain > best_gain:
                    best_gain = potential_gain
                    best_letter = letter_val
                num += prefix_count[letter_val]
            add2 += best_gain
            local_count[best_letter] += 1

        # 判断放入 candidate 后是否能满足总逆序对数要求
        if current_inversions[0] + add1 + add2 >= V:
            # 更新当前逆序对数，加上与之前字符形成的逆序对
            current_inversions[0] += add1
            return True
        else:
            # 撤销 candidate 的放置
            prefix_count[candidate] -= 1
            return False

    # 构造答案字符串，逐个位置确定字符
    result_chars = []
    for pos in range(length):
        # 尝试从字母 'a' 到 'z'（对应 1~26）的顺序，
        # 若放入某个候选字母后后续仍能达到目标，则确定该位置的字符
        for candidate in range(1, 27):
            if check_candidate(candidate, length - pos - 1):
                # 将数字 candidate 转换为对应字符
                result_chars.append(chr(candidate + ord('a') - 1))
                break

    return "".join(result_chars)


# --- 测试示例 ---
if __name__ == '__main__':
    # 例如，输入幸运数字 V
    V = int(input())
    result_string = construct_max_string(V)
    print(result_string)
